# -*- coding: utf-8 -*-
"""
Created on Sun Oct 28 08:24:58 2018

@author: geyang
@email: 302756880@qq.com
"""

class LNode:
    
    def __init__(self, element, next_ = None):
        self.element = element
        self.next = next_
        
#print(LNode(5).element)

class ArgumentsMistakeError(ValueError):
    pass

class LinkedListAdv:
    """This is an implemention of advanced linked list
    
    与标准的链表不同，改进版的链表在删除和插入尾元素时，时间复杂度为O(1)
    """
    
    def __init__(self, head = None, rear = None):
        self.head = head
        self.rear = rear
        # TypeError: 'int' object is not callable 
        # 解决：变量名不要和函数名一样
        self.list_length = 0    
    
    def isEmpty(self):
        if self.head is None and self.length() == 0:
            return True
        return False
    
    def length(self):
        return self.list_length
    
    def createList(self, elements):
        """create linked list with a given elements list
        
        arguments: elements [1,2,3,4]
        """
        # if the linked list exists, return 
        if self.head is not None:
            return
        
        # if the linked list does not exist
        p = self.head
        for i in range(len(elements)):
            node = LNode(i)
            if p is None:
                p = node
                return
            p.next = node
            p = p.next
    
    def prepend(self, element):
        """ add element at the beginning of a linked list
        """
        # if the linked list dose not exist
        if self.head is None:
            self.head = LNode(element)
            self.rear = self.head
            return
        # if the linked list exists
        self.head = LNode(element, self.head)
        
    
    def append(self, element):
        """add element at the end of a linked list
        """
        if self.head is None:
            self.head = LNode(element)
            self.rear = self.head
            return
        # if the linked list exists
        node = LNode(element)
        self.rear.next = node
        self.rear = node
            
    
    def insert(self, element, index):
        """insert a element to the linked list at given index
        """
        p = self.head
        # no element
        if p is None:
            if index != 0:
                raise ArgumentsMistakeError
            p = LNode(element)
            self.head = p
            self.rear = p
            return
        # one element
        if p.next is None:
            if index == 0:
                p = LNode(element, p)
                self.head = p
                return
            else:
                node = LNode(element)
                p.next = node
                self.rear = node
                return
        # more element
        count = 0
        while p is not None :
            if count == index - 1:
                p.next = LNode(element, p.next)
                return
            p = p.next
            count += 1
            
            
    
    def deleteFirst(self):
        if self.head is None:
            return
        self.head = self.head.next
    
    def deleteLast(self):
        p = self.head
        # no element or only one element
        if p is None or p.next is None:
            self.head = self.rear = None
            return
        # two or more element
        while p is not None:
            if p.next == self.rear:
                p.next = None
                self.rear = p
            p = p.next
                
    
    def printAll(self):
        """print linked list
        """
        result = []
        p = self.head
        while p is not None:
            result.append(p.element)
            p = p.next
        return result
            
    
    
        